package hash;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by JiaJia on 2019/5/25 0025.
 * 最长连续序列
 * Given [100, 4, 200, 1, 3, 2],
 * The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
 */
public class LongestConsecutiveSubsequence {
    private static int longestConsecutiveSubsequence(int[] nums){
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int num:nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for (int num:nums) {
            find(map,num);
        }
        return maxCount(map);
    }
    private static int find(Map<Integer,Integer> map,int num){
        if (!map.containsKey(num))
            return 0;
        int cnt=map.get(num);
        if (cnt>1)
            return cnt;
        cnt=find(map,num+1)+1;
        map.put(num,cnt);
        return cnt;
    }
    private static int maxCount(Map<Integer,Integer> map){
        int max=0;
        for (int num:map.keySet()) {
            max=Math.max(max,map.get(num));
        }
        return max;
    }

    public static void main(String[] args) {
        int[] num={100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutiveSubsequence(num));
    }
}